Reliability versus performance for critical applications

Applications implemented on critical systems are subject to both safety critical and real-time constraints. Classically, applications are specified as precedence task graphs that must be scheduled onto a given target multiprocessor heterogeneous architecture. We propose a new method for simultaneously optimizing two objectives: the execution time and the reliability of the schedule. The problem is decomposed into two successive steps: a spatial allocation during which the reliability is maximized (randomized algorithm), and a scheduling during which the makespan is minimized (list scheduling algorithm). It allows us to produce several trade-off solutions, among which the user can choose the solution that best fits the application’s requirements. Reliability is increased by replicating adequate tasks onto well chosen processors. Our fault model assumes that processors are fail-silent, that they are subject to transient failures, and that the occurrences of failures follow a constant parameter Poisson law. We assess and validate our method by running extensive simulations on both random graphs and actual application graphs. They show that it is competitive, in terms of makespan, compared to existing reference scheduling methods for heterogeneous processors (HEFT), while providing a better reliability.     

Investigating the usability of real-time scheduling theory with the Cheddar project

This article deals with real-time critical systems modelling and verification. Real-time scheduling theory provides algebraic methods and algorithms in order to make timing constraints verifications of these systems. Nevertheless, many industrial projects do not perform analysis with real-time scheduling theory even if demand for use of this theory is large and the industrial application field is wide (avionics, aerospace, automotive, autonomous systems, …). The Cheddar project investigates why real-time scheduling theory is not used and how its usability can be increased. The project was launched at the University of Brest in 2002. In Lecture Notes on Computer Sciences, vol. 5026, pp. 240–253, 2008, we have presented a short overview of this project. This article is an extended presentation of the Cheddar project, its contributions and also its ongoing works.     

Multifidelity surrogate modeling based on radial basis functions

Multiple models of a physical phenomenon are sometimes available with different levels of approximation. The high fidelity model is more computationally demanding than the coarse approximation. In this context, including information from the lower fidelity model to build a surrogate model is desirable. Here, the study focuses on the design of a miniaturized photoacoustic gas sensor which involves two numerical models. First, a multifidelity metamodeling method based on Radial Basis Function, the co-RBF, is proposed. This surrogate model is compared with the classical co-kriging method on two analytical benchmarks and on the photoacoustic gas sensor. Then an extension to the multifidelity framework of an already existing RBF-based optimization algorithm is applied to optimize the sensor efficiency. The co-RBF method does not bring better results than co-kriging but can be considered as an alternative for multifidelity metamodeling.     

Hybrid‐impulsive second‐order sliding mode control: Lyapunov approach

Dynamic system of relative degree two controlled by discontinuous‐hybrid‐impulsive feedback in the presence of bounded perturbations is considered. The state feedback impulsive‐twisting control exhibits a uniform exact finite time convergence to the second‐order sliding mode with zero convergence time. The output feedback discontinuous control augmented by a simplified hybrid‐impulsive functions provides uniform exact convergence with zero convergence time of the system's states to a real second‐order sliding mode in the presence of bounded perturbations. Only ‘snap’ knowledge of the output derivative, that is, the knowledge of the output derivative in isolated time instants, is required. The output feedback hybrid‐impulsive control with practically implemented impulsive actions asymptotically drives the system's states to the origin. The Lyapunov analysis of the considered hybrid‐impulsive‐discontinuous system proves the system's stability. The efficacy of the proposed control technique is illustrated via computer simulations. Copyright © 2016 John Wiley & Sons, Ltd.     

Fast computation of minimal elementary decompositions of metabolic flux vectors

The concept of elementary flux vector is valuable in a number of applications of metabolic engineering. For instance, in metabolic flux analysis, each admissible flux vector can be expressed as a non-negative linear combination of a small number of elementary flux vectors. However a critical issue concerns the total number of elementary flux vectors which may be huge because it combinatorially increases with the size of the metabolic network. In this paper we present a fast algorithm that randomly computes a decomposition of admissible flux vectors in a minimal number of elementary flux vectors without explicitly enumerating all of them.     

Rational method for 3D manufacturing tolerancing synthesis based on the TTRS approach “R3DMTSyn”

During the production of new part in an industrial environment, it results in a high percentage of scrap if manufacturing planning is not carried out properly. One of the major factors responsible for this phenomenon is tolerance synthesis. In this paper, we deal with tolerance synthesis, and especially tolerance type identified after transfer. An algorithmic Rational method for 3D Manufacturing Tolerancing Synthesis (R3DMTSyn), which is based on the use of the Technologically and Topologically Related Surface (TTRS) rules, is developed. The TTRS concept helps to generate only the necessary manufacturing specification needed to guarantee the respect of the functional specification studied.The manufacturing project is modeled by a graphical representation called the SPIDER GRAPH. With the SPIDER GRAPH, all active surfaces can be detected (machined and positioning surfaces), so it is possible to identify the location of the functional surfaces used in each functional specification. The construction or the determination of the tolerancing torsor, belonging to each active surface, contributes to the selection of the adequate case of associations. A semantic study is already done to identify all possible combinations or associations needed to locate surfaces during each phases.Finally, referring to the developed TTRS_Cars_Process and in every phase, one or more manufacturing specifications are generated until finishing the treatment of all surfaces (surface belonging to the functional condition, or intermediate surfaces).     

How to improve snap-stabilizing point-to-point communication space complexity?

A snap-stabilizing protocol, starting from any configuration, always behaves according to its specification. In this paper, we are interested in the message forwarding problem in a message-switched network in which the system resources must be managed in order to deliver messages to any processor of the network. To this end, we use the information provided by a routing algorithm. In the context of an arbitrary initialization (due to stabilization), this information may be corrupted. In Cournier et al. (2009) [1], we show that there exist snap-stabilizing algorithms for this problem (in the state model). This implies that we can request the system to begin forwarding messages without losses even if routing information is initially corrupted.In this paper, we propose another snap-stabilizing algorithm for this problem which improves the space complexity of the one in Cournier et al. (2009) [1].     

Patterns for multigrid equidistributed functions: Application to general parabolas and length estimation

We show that for some special functions (called k-multigrid equidistributed functions), we can compute the limit of the frequency of patterns in the discretization of their graph, when the resolution tends to zero. This result is applied to parabolas. We deduce also that local length estimators almost never converge to the length for the parabolas.     

Loop Shifting for Loop Compaction

The idea of decomposed software pipelining is to decouple the software pipelining problem into a cyclic scheduling problem without resource constraints and an acyclic scheduling problem with resource constraints. In terms of loop transformation and code motion, the technique can be formulated as a combination of loop shifting and loop compaction. Loop shifting amounts to moving statements between iterations thereby changing some loop independent dependences into loop carried dependences and vice versa. Then, loop compaction schedules the body of the loop considering only loop independent dependences, but taking into account the details of the target architecture. In this paper, we show how loop shifting can be optimized so as to minimize both the length of the critical path and the number of dependences for loop compaction. The first problem is well-known and can be solved by an algorithm due to Leiserson and Saxe. We show that the second optimization (and the combination with the first one) is also polynomially solvable with a fast graph algorithm, variant of minimum-cost flow algorithms. Finally, we analyze the improvements obtained on loop compaction by experiments on random graphs.     

FAST: acceleration from theory to practice

Fast acceleration of symbolic transition systems (Fast) is a tool for the analysis of systems manipulating unbounded integer variables. We check safety properties by computing the reachability set of the system under study. Even if this reachability set is not necessarily recursive, we use innovative techniques, namely symbolic representation, acceleration and circuit selection, to increase convergence. Fast has proved to perform very well on case studies. This paper describes the tool, from the underlying theory to the architecture choices. Finally, Fast capabilities are compared with those of other tools. A range of case studies from the literature is investigated. This paper is mainly based on results presented at CAV 2003, TACAS 2004 and ATVA 2005.